package leetcode.递归回溯BFSDFS;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 226. 翻转二叉树
 *
 * 解决思路就是通过DFS遍历到叶子节点上，再往下遍历是 null
 * 所以会返回这个叶子节点，那么此时函数的 head 就是该叶子节点的父节点
 * 同理获取right叶子节点
 *
 * 然后交换即可
 */
public class Test226翻转二叉树 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // 遍历二叉树，然后反转他
    // 后序遍历是最简单的
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }


    /*** 其他解法  ***/

    // 先序遍历--从顶向下交换
    public TreeNode invertTree2(TreeNode root) {
        if (root == null)
            return null;
        // 保存右子树
        TreeNode rightTree = root.right;
        // 交换左右子树的位置
        root.right = invertTree(root.left);
        root.left = invertTree(rightTree);
        return root;
    }

    // 中序遍历
    public TreeNode invertTree3(TreeNode root) {
        if (root == null)
            return null;
        invertTree(root.left); // 递归找到左节点
        TreeNode rightNode = root.right; // 保存右节点
        root.right = root.left;
        root.left = rightNode;
        // 递归找到右节点 继续交换 : 因为此时左右节点已经交换了,所以此时的右节点为root.left
        invertTree(root.left);
        return root;
    }

    // 层次遍历--直接左右交换即可
    public TreeNode invertTree4(TreeNode root) {

        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode rightTree = node.right;
            node.right = node.left;
            node.left = rightTree;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return root;
    }
}
